题解 CF765E Tree Folding

发表于 | 更新于

题意：给你一棵树，可以把树上父亲相同的两条长度相同的链合并。（如图）问你最后能不能变成一条链，能的话求链的最短长度。

显然如果可以合并，那么合并后长度一定$\leqslant$直径的一半，所以，我们找到直径的中点作为根(若有两个中点则随便选一个)

对于每个点(除根以外)，如果它有两条或以上长度为不同的子节点形成的链，那么这棵树是无法合并的，输出$-1$，否则用一个$set$维护子节点形成的链长度情况，向上个节点传递$set$中链的长度$+1$

特别的，对于根，因为它没有父亲节点，所以即使它有两条子节点形成的链，也是合法的(但是如果有三条及以上就不合法了)，如果有一条链，返回这条链的长度$+1$，如果有两条链，返回两条链长度之和$+2$；

最后，对于答案，如果$ans$是$2$的倍数，将它不停地除以$2$，直到$ans$是奇数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
struct node{
    int to,next;
}e[700000];
inline void write(int x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
inline void wln(int x) {write(x);puts("");}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int cnt,head[500000],dep[400005][3],mx,loc,mid;
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa,int t){
    dep[u][t]=dep[fa][t]+1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;
        dfs(v,u,t);
    }
    if (dep[u][t]>mx){
        mx=dep[u][t];
        loc=u;
    }
}
int dfs1(int u,int fa){
    set<int>lxy666;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v!=fa) lxy666.insert(dfs1(v,u));
    }
    if (u==fa){//根特殊处理
        if (!lxy666.size())return 0;
        else if (lxy666.size()==1)return *lxy666.begin()+1;
        else if (lxy666.size()==2)return *lxy666.begin()+*--lxy666.end()+2;
        else{
            puts("-1");exit(0);
        }
    }else{
        if (!lxy666.size())return 0;
        else if (lxy666.size()==1)return *lxy666.begin()+1;
        else{
            puts("-1");exit(0);
        }
    }
}
int main(){
    int n=read();
    for (int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    mx=0;
    dfs(1,0,2);
    mx=0;
    dfs(loc,0,1);
    int len=mx-1;mx=0;
    dfs(loc,0,0);
    for (int i=1;i<=n;++i)
        if (dep[i][1]+dep[i][0]-2==len){
            if (abs(dep[i][0]-dep[i][1])==0||abs(dep[i][0]-dep[i][1])==1){
                mid=i;break;
            }
        }//以上为找直径中点
    int ans=dfs1(mid,mid);while(!(ans&1))ans>>=1;
    printf("%d",ans);
    return 0;
}